import com.sun.javafx.image.IntPixelGetter;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-09
 * Time: 22:06
 */

class LRUCache {

    /**
     手写一个链表实现O(1)
     */
    class LinkedListNode{
        int key;
        int value;
        LinkedListNode prev;
        LinkedListNode next;
        public LinkedListNode(){}
        public LinkedListNode(int key,int value){
            this.key=key;
            this.value=value;
        }
    }


    //map记录key,和对应的节点
    private Map<Integer,LinkedListNode> map;
    //链表上多添上头节点和尾节点,更加简便进行头插和尾删
    private LinkedListNode head;
    private LinkedListNode tail;
    private int capacity;//大小
    public LRUCache(int capacity) {
        this.map=new HashMap<>();
        this.head=new LinkedListNode();
        this.tail=new LinkedListNode();
        this.head.next=this.tail;
        this.tail.prev=this.head;
        this.capacity=capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            //存在这个节点,拿到这个节点
            LinkedListNode node=map.get(key);
            //放到最前面
            move(node);
            //返回结果
            return node.value;
        }
        //不存在这个节点直接返回-1
        return -1;
    }

    public void put(int key, int value) {
        //如果map中存在这个节点
        if(map.containsKey(key)){
            //拿到这个节点
            LinkedListNode node=map.get(key);
            //修改value
            node.value=value;
            //移动到最前面
            move(node);
            return;
        }
        //map中不存在这个节点
        //先判断是不是满了
        if(map.size()==this.capacity){
            //满了就删除最后一个节点
            //先删除map中的值
            map.remove(this.tail.prev.key);
            //再删除链表中的节点
            this.tail.prev=this.tail.prev.prev;
            this.tail.prev.next=this.tail;
        }
        LinkedListNode newNode=new LinkedListNode(key,value);
        //添加到map中
        map.put(key,newNode);
        //添加到链表最前面
        newNode.next=this.head.next;
        this.head.next.prev=newNode;
        this.head.next=newNode;
        newNode.prev=this.head;
    }


    /**
     将节点移动到最前面
     */
    public void move(LinkedListNode node){
        //先断开与后面的连接
        node.prev.next=node.next;
        node.next.prev=node.prev;
        //再与头节点连接
        node.next=this.head.next;
        node.next.prev=node;
        this.head.next=node;
        node.prev=head;
    }
}